package 热题100.链表.合并两个有序链表_21_简单;
import 链表.两两交换链表中的节点_24.Solution.ListNode;
/*
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路：
    第一眼就想到归并排序的方式。
    需要注意的是，答案链表也要随着节点往后走，那么就要有一个开始节点来记录答案节点的起始位置
    最后返回起始位置的next就可以。
* */
public class Solution {
    public static void main(String[] args) {
        ListNode[] headB = new ListNode[3];
        ListNode[] headA = new ListNode[4];
        headA[3] = new ListNode(4,null);
        headA[2] = new ListNode(3,headA[3]);
        headA[1] = new ListNode(2,headA[2]);
        headA[0] = new ListNode(1,headA[1]);

        headB[2] = new ListNode(4,null);
        headB[1] = new ListNode(3,headB[2]);
        headB[0] = new ListNode(1,headB[1]);

        ListNode ans = mergeTwoLists(headA[0], headB[0]);
        while (ans != null){
            System.out.println(ans.val);
            ans = ans.next;
        }
    }

    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode ans = new ListNode(-1);
        // 记录答案节点的开始节点
        ListNode res = ans;
        // 判断是否为空
        ListNode first = list1, second = list2;
        if (first == null && second == null){
            return null;
        }
        while (first != null && second != null){
            if (first.val < second.val){
                ans.next = first;
                ans = ans.next;
                first = first.next;
            } else {
                ans.next = second;
                ans = ans.next;
                second = second.next;
            }
        }
        if (first != null){
            ans.next = first;
        }
        if (second != null){
            ans.next = second;
        }
        return res.next;
    }

}
